import java.util.*;

class Node {
    int data;
    Node next;
    Node prev;

    public Node(int data, Node next, Node prev) {
        this.data = data;
        this.next = next;
        this.prev = prev;
    }
}

public class DouForHeadSortList {
    static public Scanner sc = new Scanner(System.in);

    static public void p(String format, Object ... obj) {
        System.out.printf(format, obj);
    }

    static public void main(String [] args) {
        int num;
        Node head = new Node(0, null, null), newNode = null, tail = null;

        head.next = head;
        head.prev = head;

        while (true) {
            p("请输入数字(-1为退出): ");
            num = sc.nextInt();

            if (num == -1)
                break;

            tail = head;
            while (tail.next != head && tail.next.data < num) {
                tail = tail.next;
            }

            newNode = new Node(num, tail.next, tail);
            tail.next.prev = newNode;
            tail.next = newNode;
        }

        for (tail = head.next; tail != head; tail = tail.next) {
            System.out.printf("%d ", tail.data);
        }
        System.out.println();

        for (tail = head.prev; tail != head; tail = tail.prev) {
            System.out.printf("%d ", tail.data);
        }
        System.out.println();
    }
}
